Linux Multiprocessor Schedulers
You will learn about the three Linux multiprocessor schedulers in this lesson in a concise manner.
We'll cover the following
Three different multiprocessor schedulers#
Interestingly, in the Linux community, no common solution has approached building a multiprocessor scheduler. Over time, three different schedulers arose: the O(1) scheduler, the Completely Fair Scheduler (CFS), and the BF Scheduler (BFS). See Meehean’s dissertation for an excellent overview of the strengths and weaknesses of said schedulers; here we just summarize a few of the basics.
Approaches used by the schedulers#
Both O(1) and CFS use multiple queues, whereas BFS uses a single queue, showing that both approaches can be successful. Of course, there are many other details which separate these schedulers. For example, the O(1) scheduler is a priority-based scheduler (similar to the MLFQ discussed before), changing a process’s priority over time and then scheduling those with the highest priority in order to meet various scheduling objectives; interactivity is a particular focus. CFS, in contrast, is a deterministic proportional-share approach (more like Stride scheduling, as discussed earlier). BFS, the only single-queue approach among the three, is also proportional-share, but based on a more complicated scheme known as Earliest Eligible Virtual Deadline First (EEVDF). Read more about these modern algorithms on your own; you should be able to understand how they work now!
Multi-Queue Scheduling
Summary